home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / RCS / malloc.c,v < prev    next >
Encoding:
Text File  |  1991-11-12  |  9.9 KB  |  453 lines
  1. head     1.6;
  2. branch   ;
  3. access   ;
  4. symbols  sprited:1.6.1;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.6
  10. date     88.08.20.21.09.18;  author ouster;  state Exp;
  11. branches 1.6.1.1;
  12. next     1.5;
  13.  
  14. 1.5
  15. date     88.07.27.17.59.04;  author ouster;  state Exp;
  16. branches ;
  17. next     1.4;
  18.  
  19. 1.4
  20. date     88.07.25.11.10.51;  author ouster;  state Exp;
  21. branches ;
  22. next     1.3;
  23.  
  24. 1.3
  25. date     88.05.21.16.18.02;  author ouster;  state Exp;
  26. branches ;
  27. next     1.2;
  28.  
  29. 1.2
  30. date     88.05.21.11.36.59;  author ouster;  state Exp;
  31. branches ;
  32. next     1.1;
  33.  
  34. 1.1
  35. date     88.05.20.15.49.28;  author ouster;  state Exp;
  36. branches ;
  37. next     ;
  38.  
  39. 1.6.1.1
  40. date     91.08.30.15.40.30;  author kupfer;  state Exp;
  41. branches ;
  42. next     ;
  43.  
  44.  
  45. desc
  46. @@
  47.  
  48.  
  49. 1.6
  50. log
  51. @Eliminate declarations that are in MemData.c
  52. @
  53. text
  54. @/* 
  55.  * malloc.c --
  56.  *
  57.  *    Source code for the "malloc" library procedure.  See memInt.h
  58.  *    for overall information about how the allocator works.
  59.  *
  60.  * Copyright 1985, 1988 Regents of the University of California
  61.  * Permission to use, copy, modify, and distribute this
  62.  * software and its documentation for any purpose and without
  63.  * fee is hereby granted, provided that the above copyright
  64.  * notice appear in all copies.  The University of California
  65.  * makes no representations about the suitability of this
  66.  * software for any purpose.  It is provided "as is" without
  67.  * express or implied warranty.
  68.  */
  69.  
  70. #ifndef lint
  71. static char rcsid[] = "$Header: malloc.c,v 1.5 88/07/27 17:59:04 ouster Exp $ SPRITE (Berkeley)";
  72. #endif not lint
  73.  
  74. #include "stdlib.h"
  75. #include "memInt.h"
  76.  
  77.  
  78. /*
  79.  * ----------------------------------------------------------------------------
  80.  *
  81.  * malloc --
  82.  *
  83.  *    This procedure allocates a chunk of memory.
  84.  *
  85.  * Results:
  86.  *    The return value is a pointer to an area of at least bytesNeeded
  87.  *    bytes of free storage.  If no memory is available, then this
  88.  *    procedure will never return:  the MemChunkAlloc procedure 
  89.  *    determines what will happen.
  90.  *
  91.  * Side effects:
  92.  *    The returned block is marked as allocated and will not be
  93.  *    allocated to anyone else until it is returned with a call
  94.  *    to free.
  95.  *
  96.  * ----------------------------------------------------------------------------
  97.  */
  98.  
  99. ENTRY Address
  100. malloc(bytesNeeded)
  101.     register unsigned bytesNeeded;    /* How many bytes to allocate. */
  102. {
  103.     int            thisBlockSize, admin;
  104.     register Address    result;
  105.     Address        newRegion;
  106.     int            regionSize;
  107.     int            origSize;
  108.     register int    index;
  109.  
  110.     LOCK_MONITOR;
  111.  
  112. #ifdef MEM_TRACE
  113.     mem_NumAllocs++;
  114. #endif
  115.  
  116.     if (!memInitialized) {
  117.     MemInit();
  118.     }
  119.  
  120.     origSize = bytesNeeded;
  121.  
  122.     /* 
  123.      * Handle binned objects quickly, if possible.
  124.      */
  125.  
  126.     bytesNeeded = BYTES_TO_BLOCKSIZE(bytesNeeded);
  127.     index = BLOCKSIZE_TO_INDEX(bytesNeeded);
  128.     if (bytesNeeded <= BIN_SIZE) {
  129.     result = memFreeLists[index];
  130.     if (result == NOBIN) {
  131.         goto largeBlockAllocator;
  132.     }
  133.     if (result == (Address) NULL) {
  134.  
  135.         /*
  136.          * There aren't currently any free objects of this size.
  137.          * Call the client's function to obtain another region
  138.          * from the system.  While we're at it, get a whole bunch
  139.          * of objects of this size once and put all but one back
  140.          * on the free list.
  141.          */
  142.  
  143.         regionSize = BLOCKS_AT_ONCE * bytesNeeded;
  144.         newRegion = MemChunkAlloc(regionSize);
  145.  
  146.         while (regionSize >= bytesNeeded) {
  147.         SET_ADMIN(newRegion, memFreeLists[index]);
  148.         memFreeLists[index] = newRegion;
  149.         mem_NumBlocks[index] += 1;
  150.         newRegion += bytesNeeded;
  151.         regionSize -= bytesNeeded;
  152.         }
  153.         result = memFreeLists[index];
  154.     }
  155.  
  156.     memFreeLists[index] = (Address) GET_ADMIN(result);
  157.     SET_ADMIN(result, MARK_DUMMY(bytesNeeded));
  158.  
  159. #ifdef MEM_TRACE
  160.     mem_NumBinnedAllocs[index] += 1;
  161.     SET_PC(result);
  162.     SET_ORIG_SIZE(result, origSize);
  163.     MemDoTrace(TRUE, result, (Address)NULL, bytesNeeded);
  164. #endif MEM_TRACE
  165.  
  166.     UNLOCK_MONITOR;
  167.     return(result+sizeof(AdminInfo));
  168.     }
  169.  
  170.     /*
  171.      * This is a large object.  Step circularly through the blocks
  172.      * in the list, looking for one that's large enough to hold
  173.      * what's needed.
  174.      */
  175.  
  176. largeBlockAllocator:
  177.     if (origSize == 0) {
  178.     return (Address) NULL;
  179.     }
  180. #ifdef MEM_TRACE
  181.     mem_NumLargeAllocs += 1;
  182. #endif
  183.     result = memCurrentPtr;
  184.     while (TRUE) {
  185.     Address nextPtr;
  186.  
  187. #ifdef MEM_TRACE
  188.     mem_NumLargeLoops += 1;
  189. #endif
  190.     admin = GET_ADMIN(result);
  191.     thisBlockSize = SIZE(admin);
  192.     nextPtr = result+thisBlockSize;
  193.     if (!IS_IN_USE(admin)) {
  194.     
  195.         /*
  196.          * Several blocks in a row could have been freed since the last
  197.          * time we were here.  If so, merge them together.
  198.          */
  199.  
  200.         while (!IS_IN_USE(GET_ADMIN(nextPtr))) {
  201.         thisBlockSize += SIZE(GET_ADMIN(nextPtr));
  202.         admin = MARK_FREE(thisBlockSize);
  203.         SET_ADMIN(result, admin);
  204.         nextPtr = result+thisBlockSize;
  205.         }
  206.         if (thisBlockSize >= bytesNeeded) {
  207.         break;
  208.         }
  209.         if (thisBlockSize > memLargestFree) {
  210.         memLargestFree = thisBlockSize;
  211.         }
  212.     }
  213.  
  214.     /*
  215.      * This block won't do the job.  Go on to the next block.
  216.      */
  217.  
  218.     if (nextPtr != memLast) {
  219.         result = nextPtr;
  220.         continue;
  221.     }
  222.  
  223.     /*
  224.      * End of the list.  If there's any chance that there's
  225.      * enough free storage in the list to satisfy the request,
  226.      * then go back to the beginning of the list and start
  227.      * again.
  228.      */
  229.  
  230.     if ((memLargestFree + memBytesFreed) > bytesNeeded) {
  231.         memLargestFree = 0;
  232.         memBytesFreed = 0;
  233.         result = memFirst;
  234.         continue;
  235.     }
  236.  
  237.     /*
  238.      * Not enough free space in the list.  Allocate a new region
  239.      * of memory and add it to the list.
  240.      */
  241.  
  242.     if (bytesNeeded < MIN_REGION_SIZE) {
  243.         regionSize = MIN_REGION_SIZE;
  244.     } else {
  245.         regionSize = bytesNeeded + sizeof(AdminInfo);
  246.     }
  247.     newRegion = MemChunkAlloc(regionSize);
  248.     mem_NumLargeBytes += regionSize;
  249.  
  250.     /*
  251.      * If the new region immediately follows the end of the previous
  252.      * region, merge them together.  At this point result always
  253.      * points to a block of memory adjacent to and preceding the block
  254.      * of memory pointed to by memLast (memLast == nextPtr).  Thus it
  255.      * may be possible to merge the new region with both the region
  256.      * at result and the one at nextPtr.
  257.      */
  258.  
  259.     if (newRegion == (nextPtr+sizeof(AdminInfo))) {
  260.         newRegion = nextPtr;
  261.         regionSize += sizeof(AdminInfo);
  262.         if (!IS_IN_USE(admin)) {
  263.         newRegion = result;
  264.         regionSize += SIZE(admin);
  265.         }
  266.     } else {
  267.         SET_ADMIN(nextPtr, MARK_DUMMY(newRegion - nextPtr));
  268.     }
  269.  
  270.     /*
  271.      * Create a dummy block at the end of the new region, which links
  272.      * to "last".
  273.      */
  274.     
  275.     SET_ADMIN(newRegion, MARK_FREE(regionSize - sizeof(AdminInfo)));
  276.     memLast = newRegion + regionSize - sizeof(AdminInfo);
  277.     SET_ADMIN(memLast, MARK_DUMMY(0));
  278.  
  279.     /*
  280.      * Continue scanning the list (try result again in case it
  281.      * merged with the new region).
  282.      */
  283.     }
  284.  
  285.     /*
  286.      * At this point we've got a block that's large enough.  If it's
  287.      * larger than needed for the object, put the rest back on the
  288.      * free list (note: even if the remnant is smaller than the smallest
  289.      * large object, which means it'll be used by itself, we put it back
  290.      * on the list so it can merge with either this block or the next,
  291.      * whichever gets freed first).
  292.      */
  293.  
  294.     if (thisBlockSize < (bytesNeeded + sizeof(AdminInfo))) {
  295.     SET_ADMIN(result, MARK_IN_USE(admin));
  296.     } else {
  297.     SET_ADMIN(result+bytesNeeded, MARK_FREE(thisBlockSize-bytesNeeded));
  298.     SET_ADMIN(result, MARK_IN_USE(bytesNeeded));
  299.     }
  300.  
  301. #ifdef MEM_TRACE
  302.     SET_PC(result);
  303.     SET_ORIG_SIZE(result, origSize);
  304.     MemDoTrace(TRUE, result, (Address) NULL, bytesNeeded);
  305. #endif MEM_TRACE
  306.     memCurrentPtr = result;
  307.  
  308.     UNLOCK_MONITOR;
  309.     return(result+sizeof(AdminInfo));
  310. }
  311. @
  312.  
  313.  
  314. 1.6.1.1
  315. log
  316. @Initial branch for Sprite server.
  317. @
  318. text
  319. @d18 1
  320. a18 1
  321. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/malloc.c,v 1.6 88/08/20 21:09:18 ouster Exp $ SPRITE (Berkeley)";
  322. @
  323.  
  324.  
  325. 1.5
  326. log
  327. @Use C library convention:  unsigned arg to malloc.
  328. @
  329. text
  330. @d18 1
  331. a18 1
  332. static char rcsid[] = "$Header: malloc.c,v 1.4 88/07/25 11:10:51 ouster Exp $ SPRITE (Berkeley)";
  333. a23 28
  334. /*
  335.  * Info for binned allocation.  See memInt.h for details.
  336.  */
  337.  
  338. Address        memFreeLists[BIN_BUCKETS];
  339. int        mem_NumBlocks[BIN_BUCKETS];
  340. #ifdef MEM_TRACE
  341. int        mem_NumBinnedAllocs[BIN_BUCKETS];
  342. #endif
  343.  
  344. /*
  345.  * Info for large-block allocator.  See memInt.h for details.
  346.  */
  347.  
  348. Address        memFirst, memLast;
  349. Address        memCurrentPtr;
  350. int        memLargestFree = 0;
  351. int        memBytesFreed = 0;
  352. int        mem_NumLargeBytes = 0;
  353. int        mem_NumLargeAllocs = 0;
  354. int        mem_NumLargeLoops = 0;
  355.  
  356. int        mem_NumAllocs = 0;
  357. int        mem_NumFrees = 0;
  358.  
  359. int        memInitialized = 0;
  360.  
  361. Sync_Lock    memMonitorLock;
  362. @
  363.  
  364.  
  365. 1.4
  366. log
  367. @Lint.
  368. @
  369. text
  370. @d18 1
  371. a18 1
  372. static char rcsid[] = "$Header: malloc.c,v 1.3 88/05/21 16:18:02 ouster Exp $ SPRITE (Berkeley)";
  373. d76 1
  374. a76 1
  375.     register int bytesNeeded;        /* How many bytes to allocate. */
  376. @
  377.  
  378.  
  379. 1.3
  380. log
  381. @Temporarily add a guarantee that Mem_Size will be linked in always.
  382. @
  383. text
  384. @d18 1
  385. a18 1
  386. static char rcsid[] = "$Header: malloc.c,v 1.2 88/05/21 11:36:59 ouster Exp $ SPRITE (Berkeley)";
  387. a285 24
  388.  
  389. /*
  390.  * Everything below here is a temporary kludge, needed while the new
  391.  * library is being developed, so that the new and old libraries can
  392.  * coexist peacefully.  Once the new library is complete, this stuff
  393.  * should all be deleted.
  394.  */
  395.  
  396. Address
  397. Mem_Alloc(numBytes)
  398.     int numBytes;
  399. {
  400.     return (Address) malloc((unsigned) numBytes);
  401. }
  402.  
  403. void
  404. Mem_Free(blockPtr)
  405.     Address blockPtr;
  406. {
  407.     free(blockPtr);
  408. }
  409.  
  410. static char * (*dummyProc)() = calloc;
  411. static int (*dummyProc2)() = Mem_Size;
  412. @
  413.  
  414.  
  415. 1.2
  416. log
  417. @Give initial values to variables.  Bizarre as it may seem, this
  418. is necessary to keep old malloc stuff from being drawn in during
  419. links (uninitialized variables are treated sort of like undefined
  420. in terms of drawing in library files).
  421. @
  422. text
  423. @d18 1
  424. a18 1
  425. static char rcsid[] = "$Header: malloc.c,v 1.1 88/05/20 15:49:28 ouster Exp $ SPRITE (Berkeley)";
  426. d309 1
  427. @
  428.  
  429.  
  430. 1.1
  431. log
  432. @Initial revision
  433. @
  434. text
  435. @d18 1
  436. a18 1
  437. static char rcsid[] = "$Header: proto.c,v 1.2 88/03/11 08:39:08 ouster Exp $ SPRITE (Berkeley)";
  438. d40 5
  439. a44 5
  440. int        memLargestFree;
  441. int        memBytesFreed;
  442. int        mem_NumLargeBytes;
  443. int        mem_NumLargeAllocs;
  444. int        mem_NumLargeLoops;
  445. d46 2
  446. a47 2
  447. int        mem_NumAllocs;
  448. int        mem_NumFrees;
  449. d49 1
  450. a49 1
  451. int        memInitialized;
  452. @
  453.